package Ep05_StackAndQueue._0347;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/4/14 12:00
 * 说明：map + 大小顶堆解法 ----> 推荐
 */

public class Best {
    // 推荐：性能更好
    // 大顶堆实现，使用优先级队列，大数置前，然后add所有map元素，最后pop前k个元素
    public int[] topKFrequent1(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 大顶堆写法
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++){
            res[i] = pq.poll()[0];
        }
        return res;
    }



    // 小顶堆实现，使用优先级队列，小数置前，add map中的元素时，超过k个就pop，即把最小的元素从堆顶pop出去
    public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 小顶堆写法，形参与 重写Comparator、lambda表达式 等效
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            if (pq.size() < k){
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                // 剪枝：如果出现频率比堆顶的频率还少，就不用进来了直接pass。
                if (entry.getValue() > pq.peek()[1]){
                    pq.poll();
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[] res = new int[k];
        for (int i = k-1; i >= 0; i--) {
            res[i] = pq.poll()[0];
        }
        return res;
    }
}
